package leetcodev1.数组;

//数组去重问题
class Solution {
    //数组思路
    //时间点：当前元素不等于过去元素的时候
    //思路1：双指针 维护有效的指针和遍历指针 满足条件后swap一下
    //思路2：双指针 但是指针2很难维护，可以通过指针2=指针1-个数

    //输入：0,1,0,3,12
    //输出：1,3,12,0,0
    //定义[0,nonZeroIndex]中的为非0元素
    public void moveZeroes1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int nonZeroIndex = 0;
        //非0元素插入数组
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[nonZeroIndex++] = nums[i];
            }
        }

        //将剩下的位数format成0
        for (int i = nonZeroIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    //输入：0,1,0,3,12
    //输出：1,3,12,0,0
    //双指针算法
    //指针1遇0就不走
    //指针2正常遍历
    //swap两个元素
    public void moveZeroes2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        int j = 0;//统计前面0的个数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;

                j++;
            }
        }

    }

    //定义j为0的个数
    //[0,nums.length-j]为非0区间
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        int j = 0;//统计前面0的个数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                j++;
            } else if (j != 0) {
                //i-j=非0的真实位置
                nums[i - j] = nums[i];
                nums[i] = 0;
            }
        }

    }

    //原地移除val的元素，并返回修改后的数组长度
    //valCount为val的数量
    //其中元素真实位置 = j - valCount
    public int removeElement1(int[] nums, int val) {
        int valCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                //更新val个数
                valCount++;
            } else if (valCount != 0) {
                nums[i - valCount] = nums[i];//真实的位置
                nums[i] = 0;//空位补0
            }
        }
        return nums.length - valCount;
    }

    public int removeElement2(int[] nums, int val) {
        //j代表下一次插入的位置
        //这里的j = i-重复元素
        int i, j = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }

    //题目
    //升序数组
    //原地删除
    //删除重复元素
    //输入 [1,1,2]
    //输出 [1,2,0]
    //分析 相当于上面的removeElement 不过会根据每次起始值进行变化
    public int removeDuplicates1(int[] nums) {
        //异常处理
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int duplicateCount = 0;
        int currentCompareVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int currentVal = nums[i];
            if (duplicateCount != 0) {
                //移动到正确的位置
                nums[i - duplicateCount] = nums[i];
                nums[i] = 0;
            }

            if (currentCompareVal == currentVal) {
                //记录重复元素个数
                duplicateCount++;
            } else {
                //更新当前val
                currentCompareVal = currentVal;
            }

        }

        return nums.length - duplicateCount;
    }

    //j代表插入合适的位置
    public int removeDuplicates2(int[] nums) {
        //至少一个不重复元素
        int j = 1;
        for (int i = 1; i < nums.length; i++) {
            //不重复元素
            if (nums[i] != nums[i - 1]) {
                //填充到合适的位置
                nums[j++] = nums[i];
            }
        }
        return j;
    }

    //和刚才的题一样，不过最多剩2个
    public int removeDuplicates(int[] nums) {
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            if (len < 2 || nums[i] != nums[len - 2]) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }

}
